ГРАФЫ

Фигура образованная конечным набором точек плоскости и отрезков, соединяю­щих некоторые из этих точек, называется плоским графом, или просто графом (рис. 2.1, а). Точки называются вершинами, а отрезки – ребрами графа.

Вместо отрезков в качестве ребер графов рассматриваются также кривые линии на плоскости (рис. 2.1, б).

Примерами графов могут служить схемы метрополитена, железных и шоссейных дорог, планы выставок и т.д. С помощью графов указываются различные связи между объектами.

Исторически сложилось так, что теория графов зародилась в ходе решения головоломок двести с лишним лет назад.

Одной из таких задач-головоломок была задача о кенигсбергских мостах, которая привлекла к себе внимание Леонарда Эйлера (1707-1783), долгое время жившего и работавшего в России (с 1727 по 1741 год и с 1766 до конца жизни).

Задача. В г. Кёнигсберге (ныне Калининград) было семь мостов через реку Прегель (рис. 2.2, где Л - левый берег, П - правый берег, А и Б - острова). Задача заключалась в следующем: можно ли, прогуливаясь по городу, пройти через каждый мост ровно один раз?

Эта задача связана с другими головоломками, суть которых заключа­лась в том, чтобы обвести контур некоторой фигуры, не отрывая каранда­ша от бумаги и не обводя ни одной линии контура дважды, т.е. "нарисо­вать одним росчерком". Такие контуры образуют так называемые уникур­сальные графы.

Задаче о кёнигсбергских мостах Л. Эйлер посвятил целое исследова­ние, которое в 1736 году было представлено в Петербургскую Академию наук.

На рисунке 2.3 изображен граф, соответствующий задаче о кёнигс­бергских мостах. Требуется доказать, что этот граф является уникур­сальным.

Для этого рассмотрим понятие индекса вершины - число ребер графа, сходящихся в данной вершине, и докажем, что имеет место следующая теорема.

Теорема. Для уникурсального графа число вершин нечетного индекса равно нулю или двум.

Доказательство. Действительно, если граф уникурсален и его начало не совпадает с концом, то начало и конец являются единственными вершинами нечетного индекса. Остальные вершины имеют четный индекс, так как в каждую точку мы входим и выходим из нее. Если начало совпадает с концом, то вершин с нечетным индексом нет.

Приступим теперь к решению задачи. Определим четность вершин гра­фа на рисунке 2.3. Вершина А имеет индекс 5, Б - 3, П - 3 и Л - 3. Таким образом, мы имеем четыре вершины нечетного индекса, и, следова­тельно, данный граф не является уникурсальным. Отсюда получаем, что во время прогулки по городу нельзя пройти по каждому из семи мостов только один раз.

Задачи

1. Нарисуйте графы, у которых имеются вершины индексов 1, 2, 3 и 4.

2. Нарисуйте граф, в котором каждая вершина имеет индекс, равный: а) двум; б) трем; в) четырем.

3. Докажите, что в любом графе сумма индексов всех его вершин - число четное, равное удвоенному числу ребер графа. Выведите из этого, что число вершин с нечетными индексами четно.

4. В графе 6 вершин, каждая из которых имеет индекс 3. Сколько у него ребер? Нарисуйте такой граф.

5. В графе 5 вершин, каждая из которых имеет индекс 4. Сколько у него ребер? Нарисуйте такой граф.

6. Можно ли соединить семь точек отрезками так, чтобы каждая точка была соединена ровно с: а) двумя; б) тремя; в) четырьмя; г) пятью другими?

7. Сформулируйте и решите задачи, двойственные задачам 5.

8. В офисе 15 компьютеров. Можно ли соединить их друг с другом так, чтобы каждый был соединен ровно с тремя другими?

9. В государстве 100 городов. Из каждого города выходит четыре дороги. Сколько всего дорог в государстве?

10. Определите, какие графы, изображенные на рисунке 2.4, являются уникурсальными?

11. Докажите, что во всяком графе, ребрами которого являются отрезки, найдутся, по крайней мере, две вершины одинакового индекса.

12. Какое наименьшее число мостов в задаче о кёнигсбергских мостах придется пройти дважды, чтобы пройти по каждому мосту?

13. Докажите, что если в задаче о кёнигсбергских мостах добавить еще один мост в любом месте реки Прегель, то полученный граф будет уникурсальным.